# 46.全排列
# 给定一个不含重复数字的数组nums ，返回其所有可能的全排列 。你可以按任意顺序返回答案。
#
# 示例1：
# 输入：nums = [1, 2, 3]
# 输出：[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
#
# 示例2：
# 输入：nums = [0, 1]
# 输出：[[0, 1], [1, 0]]
#
# 示例3：
# 输入：nums = [1]
# 输出：[[1]]


class Solution:
    def permute(self, nums: [int]):
        res = []
        path = []
        # 自己写的，居然不需要索引
        def backtracking(nums):
            if len(path) == len(nums):
                res.append(path[:])
                return
            for i in range(len(nums)):
                if nums[i] not in path:
                    path.append(nums[i])
                    backtracking(nums)
                    path.pop()
        backtracking(nums)
        return res

    def permute2(self, nums: [int]):
        res = []
        path = []
        # 看了5分钟，了解了index和used，先来试一下
        used = [0] * len(nums)
        def backtracking(nums,index):
            if len(path) == len(nums):
                res.append(path[:])
                return
            for i in range(index,len(nums)):
                if not used[i]: # 避免取重复元素
                    path.append(nums[i])
                    used[i] = 1
                    backtracking(nums,0) # 每次遍历都是从头开始
                    used[i] = 0
                    path.pop()
        backtracking(nums,0)
        return res

    def permute3(self, nums: [int]):
        # 卡哥的写法
        res = []
        path = []
        # 看了5分钟，了解了index和used，先来试一下
        used = [0] * len(nums)
        def backtracking(nums,used):
            if len(path) == len(nums):
                res.append(path[:])
                return
            for i in range(0,len(nums)):
                if used[i] == 1:
                    continue
                used[i] = 1
                path.append(nums[i])
                backtracking(nums, used)  # 每次遍历都是从头开始
                used[i] = 0
                path.pop()
        backtracking(nums,used)
        return res


if __name__ == '__main__':
    nums = [1, 2, 3]
    # nums.remove(nums)
    tmp = Solution()
    # res = tmp.permute(nums)
    # res = tmp.permute2(nums)
    res = tmp.permute3(nums)
    print(res)